/************************************************************************

								Heroes IV
					  Copyright 2001, The 3DO Company

	------------------------------------------------------------------
  						 combat_ai.h

	$Header: $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "combat_ai.h"

#include <algorithm>
#include <float.h>
#include <functional>
#include <limits>
#include "abstract_combat_ai_action.h"
#include "adventure_map.h"
#include "angle.h"
#include "area_effect_point.h"
#include "area_effect_point_ptr.h"
#include "area_effect_point_set.h"
#include "area_effect_shape.h"
#include "battlefield.h"
#include "can_cast.h"
#include "combat_ai_melee_action.h"
#include "combat_ai_move_action.h"
#include "combat_ai_defend_action.h"
#include "combat_ai_ranged_area_action.h"
#include "combat_ai_ranged_single_action.h"
#include "combat_ai_wait_action.h"
#include "combat_ai_ptr.h"
#include "combat_context.h"
#include "combat_creature.h"
#include "combat_creature_set.h"
#include "combat_spell.h"
#include "combat_spell_registration.h"
#include "combat_window.h"
#include "enum_operations.h"
#include "external_string.h"
#include "hero_keyword_replacer.h"
#include "iterator_operations.h"
#include "map_point.h"
#include "player.h"
#include "replace_keywords.h"
#include "simple_dialog.h"
#include "spell.h"
#include "town.h"

void t_abstract_combat_ai_action::set_weight( double weight )
{
	m_basic_weight = weight;
	if (weight == std::numeric_limits<double>::quiet_NaN())
	{
		m_random_weight = 0.0;
	}
	else
	{
		m_random_weight = random( weight * 0.15 );
	}
}

t_combat_ai::t_combat_ai(t_combat_creature &actor) 
	: m_actor(actor)
{
}

//--------------------------------------------------------------------
// Generate all legitimate ranged actions
//--------------------------------------------------------------------
void t_combat_ai::generate_ranged()
{
	t_battlefield &battlefield = m_actor.get_battlefield();

	if (!battlefield.can_shoot(m_actor))
		return;

	if (m_actor.is_active(k_spell_song_of_peace))
		return;

	if (m_actor.has_ability(k_ability_area_effect))
	{
		t_area_effect_shape shape;

		shape = k_area_effect_shape_5_circle;

		const t_area_effect_point_set &base_area_point_set = battlefield.get_data_cache().get_base_area_effect_point_set(shape);

		t_area_effect_point_set filtered_area_point_set;

		// Filter point set in several ways:
		// 1) Remove points which will only hit friendly creatures
		// 2) Remove points which are not in the actor's LOS
		// 3) Remove points which are definately worse that another
		//    point: either they don't include an enemy creature
		//    which the other point does, or they include a 
		//    friendly creature which the other point doesn't,
		//    or both, with no other changes
		t_area_effect_point_set::const_iterator base_iterator;
		t_area_effect_point_set::iterator filtered_iterator;

		for (base_iterator = base_area_point_set.begin(); base_iterator != base_area_point_set.end(); base_iterator++)
		{
			const t_area_effect_point &base_point = **base_iterator;

			// Test #1:
			const t_combat_creature_set &creature_set = base_point.get_affected_list();
			t_combat_creature_set::const_iterator creature_iterator;
			bool has_enemy = false;

			for (creature_iterator = creature_set.begin(); !has_enemy && creature_iterator != creature_set.end(); creature_iterator++)
			{
				if ((*creature_iterator)->belongs_to_defender() != m_actor.get_controller())
					has_enemy = true;
			}

			if (!has_enemy)
				continue;


			// Create the new attack point(s). May be more than one for different 
			// range factors

			// Map of range_factor -> area_point
			typedef std::map<int, t_area_effect_point_ptr> t_range_factor_point_map;

			t_range_factor_point_map new_point_map;

			const t_map_point_2d_list &base_location_list = base_point.get_point_list();
			t_map_point_2d_list::const_iterator base_location_iterator;

			// Test #2: Add points which are in the actor's LOS
			for (base_location_iterator = base_location_list.begin(); base_location_iterator != base_location_list.end(); base_location_iterator++)
			{
				const t_map_point_2d &location = *base_location_iterator;
				t_ranged_result obscured;

				if (battlefield.can_see_cell(m_actor, location, obscured))
				{
					int range_factor = m_actor.get_range_factor(location);
					if (obscured == k_ranged_result_obscured)
					{
						range_factor *= 2;
					}

					t_range_factor_point_map::value_type val(range_factor, 0);

					std::pair<t_range_factor_point_map::iterator, bool> insert_return = new_point_map.insert(val);

					t_area_effect_point_ptr &new_point = insert_return.first->second;

					if (new_point == NULL)
					{
						new_point = new t_area_effect_point;
						new_point->set_range_factor(range_factor);
					}

					new_point->add_point(location);
				}
			}


			// Test #3: Are any of the other area_effect_points definately 
			// better than this one? Is this one better than them? 
			// Note: Test only against filtered_area_point_set, 
			// base_area_point_set might contain better points which
			// will be knocked out by the LOS test
			for (t_range_factor_point_map::iterator new_point_iterator = new_point_map.begin();
				 new_point_iterator != new_point_map.end();
				 new_point_iterator++)
			{
				t_area_effect_point_ptr new_point = new_point_iterator->second;

				filtered_iterator = filtered_area_point_set.begin();
				bool is_bad_choice = false; // Is new_point a bad choice

				while (!is_bad_choice && filtered_iterator != filtered_area_point_set.end())
				{
					const t_area_effect_point &filtered_point = **filtered_iterator;

					if (filtered_point.get_range_factor() != new_point->get_range_factor())
					{
						filtered_iterator++;
					}
					else if (area_effect_point_is_better(filtered_point, base_point))
					{
						is_bad_choice = true;
					}
					else if (area_effect_point_is_better(base_point, filtered_point))
					{
						filtered_iterator = filtered_area_point_set.erase(filtered_iterator);
					}
					else
					{
						filtered_iterator++;
					}
				}

				if (is_bad_choice)
					continue;

				// Passed all the tests, record
				for (creature_iterator = creature_set.begin(); creature_iterator != creature_set.end(); creature_iterator++)
				{
					new_point->add_creature(*creature_iterator);
				}

				filtered_area_point_set.insert(new_point);
			}
		}

		// Create one action for each possible list of creatures
		for (filtered_iterator = filtered_area_point_set.begin(); filtered_iterator != filtered_area_point_set.end(); filtered_iterator++)
		{
			t_combat_ai_action_ptr action 
				= new t_combat_ai_ranged_area_action( battlefield, *filtered_iterator);

			consider_action( action );
		}
	}
	else
	{
		t_combat_creature_list::iterator creature_iterator; 

		// Generate one action per enemy creature
		for (creature_iterator = battlefield.creatures_begin(); creature_iterator != battlefield.creatures_end(); creature_iterator++)
		{
			t_combat_creature_ptr            target = *creature_iterator;

			// Don't attack our units, even if they are hypnotized
			if (target->belongs_to_defender() == m_actor.get_controller())
				continue;

			if (target->get_number() == 0)
				continue;

			if (target->is_active( k_spell_sanctuary ))
				continue;
			
			if (m_actor.check_cowardice( *target ))
				continue;

			int range_factor = battlefield.get_range_factor(m_actor, *target);

			if (range_factor == 0)
				continue;

			t_combat_ai_action_ptr action 
				= new t_combat_ai_ranged_single_action( battlefield, target, range_factor);

			consider_action( action );
		}
	}
}

//--------------------------------------------------------------------
// Generate all legitimate spell-casting actions
//--------------------------------------------------------------------
void t_combat_ai::generate_spell()
{
	t_spell				spell;
	t_battlefield&	battlefield = m_actor.get_battlefield();

	for (spell = t_spell(0); spell < k_spell_count; enum_incr(spell))
	{
		if (!m_actor.can_cast( spell ))
			continue;

		t_combat_spell_ptr spell_object = create_combat_spell( battlefield, spell );
		if (spell_object == NULL)
			continue;

		t_combat_ai_action_list list;

		list = spell_object->generate_combat_ai_action_list(*this);
		if (!list.empty())
			consider_action( get_best_of_list( list ) );
	}
}

//--------------------------------------------------------------------
// examine an action as possible new best action
//--------------------------------------------------------------------
void t_combat_ai::consider_action( t_abstract_combat_ai_action* action )
{
	if (action == 0)
		return;

	if (m_best_action == 0 || 
		action->get_weight( *this ) > m_best_action->get_weight( *this ))
		m_best_action = action;
}

//--------------------------------------------------------------------
// Determine best action out a list of actions
//--------------------------------------------------------------------
t_combat_ai_action_ptr t_combat_ai::get_best_of_list(t_combat_ai_action_list &list)
{
	t_combat_ai_action_ptr best_action = NULL;
	t_combat_ai_action_list::iterator action;

	for (action = list.begin(); action != list.end(); action++)
	{
		t_combat_ai_action_ptr cur = *action;

		if (!cur->get_never_use( *this ))
		{
			if (   best_action == NULL 
				|| cur->get_weight( *this ) > best_action->get_weight( *this ))
			{
				best_action = cur;
			}
		}
	}
	
	return best_action;
}

//--------------------------------------------------------------------
// Determine best of all possible actions by:
// 1) Generating all actions
// 2) Weighing all actions
// 3) Doing a linear search for the best action in the list
//--------------------------------------------------------------------
t_combat_ai_action_ptr t_combat_ai::get_best_action(void)
{
	// Step 1: Generate all actions
	m_best_action = 0;

	m_best_action = generate_best_melee_action( *this );
	generate_ranged();
	generate_spell();
	generate_move_actions( *this );

	if (m_best_action != 0)
		return m_best_action;

	t_battlefield& battlefield = m_actor.get_battlefield();

	if (!m_actor.is_waiting())
		return new t_combat_ai_wait_action( battlefield );
	return new t_combat_ai_defend_action( battlefield );
}

///////////////////////////////////////////////////////////////////////////////
// UTILITY FUNCTIONS


//--------------------------------------------------------------------
// Determine if area_effect_point p1 is always going to be better for
// an attack point than p2. 
// This is true if the the only differences between p1's creature
// list and p2's creature list are:
// (a) p1's list includes enemy creature(s) not included in p2's and/or
// (b) p2's list includes friendly creature(s) not included in p1's list.
// NOTE: it is assumed that p1 and p2 have different lists
//--------------------------------------------------------------------
bool t_combat_ai::area_effect_point_is_better(const t_area_effect_point &p1, const t_area_effect_point &p2) const
{
	t_combat_creature_set::const_iterator p1_iterator = p1.get_affected_list().begin();
	t_combat_creature_set::const_iterator p1_end      = p1.get_affected_list().end();
	t_combat_creature_set::const_iterator p2_iterator = p2.get_affected_list().begin();
	t_combat_creature_set::const_iterator p2_end      = p2.get_affected_list().end();

	while (p1_iterator != p1_end && p2_iterator != p2_end)
	{
		if (*p1_iterator == *p2_iterator)
		{
			p1_iterator++;
			p2_iterator++;
		}
		else if (*p1_iterator < *p2_iterator)
		{
			// p1 includes a creature not in p2
			if ((*p1_iterator)->belongs_to_defender() == m_actor.get_controller())
			{
				return false;
			}
			p1_iterator++;
		}
		else
		{
			// p2 includes a creature not in p1
			if ((*p2_iterator)->belongs_to_defender() != m_actor.get_controller())
			{
				return false;
			}
			p2_iterator++;
		}
	}

	while (p1_iterator != p1_end)
	{
		if ((*p1_iterator)->belongs_to_defender() == m_actor.get_controller())
		{
			return false;
		}
		p1_iterator++;
	}


	while (p2_iterator != p2_end)
	{
		if ((*p2_iterator)->belongs_to_defender() != m_actor.get_controller())
		{
			return false;
		}
		p2_iterator++;
	}

	return true;
}


//--------------------------------------------------------------------
// Determine if a given unit would interfere with another unit, given
// certain changes to the battlefield.
// interferer: Creature that might interfere
// interferee: Creature that might be interfered with
// interferer_facing: Assumed angle interferer will face
// post_attack: If true, ignore blind spells which would be 
//   canceled by any attack
// Static function
//--------------------------------------------------------------------
double t_combat_ai::would_interfere(const t_combat_creature &interferer, const t_combat_creature &interferee, int interferer_facing, bool post_attack)
{
	t_map_point_2d						   point = interferee.get_cell_position();
	t_map_point_2d						   center;
	int									   half_footprint_size;
	int									   distance;
	int									   attack_distance;
	int									   angle;
	
	// creatures in arrow towers can always shoot.
	if (interferee.is_in_tower())
		return false; 

	half_footprint_size = interferee.get_half_footprint_size();
	center = point;
	center <<= k_battlefield_subcell_shift;
	center.row += half_footprint_size;
	center.column += interferee.get_half_footprint_size();

	if (interferer.is_friendly( interferee ))
		return false;

	if (   !interferer.is_alive() 
		|| interferer.is_active( k_spell_frozen )
	    || interferer.is_active( k_spell_stun ))
		return false;

	if (!post_attack && interferer.is_active( k_spell_blind ))
		return false;



	distance = interferer.get_edge_subcell_distance( center );
	attack_distance = (interferer.get_attack_range() + 1) << k_battlefield_subcell_shift;
	if (distance > attack_distance + half_footprint_size)
		return false;

	// check angle
	angle = get_angle( interferer.get_footprint_center(), center );
	return (get_difference( angle, interferer_facing ) << 1) <= interferer.get_arc_threat();

}


//--------------------------------------------------------------------
// Get the benefit weight of removing ZOC interference from 
// friendly units. target is the subject of the attack, 
// damage is the expected damage. If turn is true, creature will
// be left facing new_angle at end of attack  
// Static function
//--------------------------------------------------------------------
double t_combat_ai::get_zoc_change_weight(int damage, const t_combat_creature &target, bool turn,
										  int new_angle)
{
	t_battlefield &battlefield = target.get_battlefield();

	// Weight from removing interference with friendly units
	double weight = 0.0;
	int target_hps = target.get_total_hits();

	assert(target_hps > 0);

	const t_combat_creature_list &target_interferes_with_list = battlefield.get_data_cache().get_creature_interferes_with_list(target);
	t_combat_creature_list::const_iterator inteferee_iterator;

	for (inteferee_iterator = target_interferes_with_list.begin(); inteferee_iterator != target_interferes_with_list.end(); inteferee_iterator++)
	{
		const t_combat_creature &interferee = **inteferee_iterator;
		double this_zoc_weight = interferee.get_interference_bonus();

		// Two possible scaling factors: 
		// 1) If interferee is still going to be in enemy ZOC, multiply by 1 - (new interfering hitpoints / old interfering hitpoints)
		double remain_scalar; // Factor #1

		// Calculate #1
		int new_interfering_hps;

		// Add in remaining interferers
		const t_combat_creature_list &interferes_with_interferee_list = battlefield.get_data_cache().get_interferes_with_creature_list(interferee);
		t_combat_creature_list::const_iterator inteferers_iterator;

		for (inteferers_iterator = interferes_with_interferee_list.begin(); inteferers_iterator != interferes_with_interferee_list.end(); inteferers_iterator++)
		{
			const t_combat_creature &interferer = **inteferers_iterator;
			if (&interferer != &target)
			{
				int hps = interferer.get_total_hits();
				new_interfering_hps += hps;
			}
		}

		int old_interfering_hps = new_interfering_hps + target_hps;

		// Is unit still in target's ZOC?

		if (   damage < target_hps
			&& (!turn || would_interfere(target, interferee, new_angle, true)))
		{
			new_interfering_hps += target_hps - damage;
		}

		remain_scalar = 1.0 - (double(new_interfering_hps) / double(old_interfering_hps));
		this_zoc_weight *= remain_scalar;
		weight += this_zoc_weight;
	}
	return weight;
}


// -----------------------------------------------------
// determine if a creature threatens the other team
// -----------------------------------------------------
bool threatens_enemies( t_combat_creature const& attacker )
{
	// can the target attack anyone this turn?
	t_battlefield&						battlefield = attacker.get_battlefield();

	if (battlefield.can_shoot( attacker ))
		return true;
	if (attacker.has_damage_spells())
		return true;

	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	t_combat_creature*					creature;
	t_ai_combat_data_cache&				data = battlefield.get_data_cache();

	for (; index != end; ++index)
	{
		creature = *index;
		// check if this is a live, friendly stack
		if (creature->get_number() == 0)
			continue;
		if (attacker.get_controller() == creature->get_controller())
			continue;

		// check if there is a position where this creature can be attacked
		// this turn
		t_attack_angle_list const& attack_angles = data.get_attack_angles( attacker, *creature );

		if (attack_angles.empty())
			continue;
		if (attack_angles.get_closest()->move_distance <= attacker.get_combat_movement())
			return true;
	}
	return false;
}

// -----------------------------------------------------
// determine if AI should retreat
// -----------------------------------------------------
static bool should_retreat( t_battlefield& battlefield, bool side )
{
	t_player* player = battlefield.get_player( side );

	if (player == 0)
		return false;

	if (player->is_computer())
	{
		t_combat_window*	combat_window = battlefield.get_combat_window();
		t_combat_context&	combat_context = *combat_window->get_context();
		t_adventure_map*	adventure_map = combat_context.get_adventure_map();
		t_difficulty		difficulty = adventure_map->get_player_difficulty();

		switch (difficulty)
		{
			case k_difficulty_easy:
				return false;

			case k_difficulty_normal:
				if (random(100) >= 50)
					return false;
				break;
		}
	}

	// check if predicted result is death, or we're not going to hurt the enemy.
	t_ai_combat_data_cache&	cache = battlefield.get_data_cache();

	bool	going_to_die = true;
	bool	enemy_hurt = false;
	bool	casualties_this_turn = false;

	// never retreat / surrender if we've got 50% or more of the enemy's strength.
	if (cache.get_total_combat_value( side ) * 2.0 > cache.get_total_combat_value( !side ))
		return false;

	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	t_combat_creature*					creature;
	int									casualty_time;

	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->get_number() == 0)
			continue;
		if (creature->belongs_to_defender() == side)
		{
			if (cache.get_approximate_lifespan( *creature ) > 1)
				going_to_die = false;
			casualty_time = cache.get_approximate_first_casualty_time( *creature );
			if (creature == battlefield.get_acting_creature())
				casualty_time--;
			if (casualty_time < 2)
				casualties_this_turn = true;
		}
		else
		{
			if (cache.get_approximate_losses( *creature ) > 0)
				enemy_hurt = true;
		}
	}
	if (!casualties_this_turn)
		return false;
	return (going_to_die || !enemy_hurt);
}

static bool no_heroes( t_battlefield& battlefield, bool side )
{
	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	t_combat_creature const*			creature;

	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->belongs_to_defender() != side || creature->is_summoned())
			continue;
		if (creature->get_hero() != 0)
			return false;
	}
	return true;
}

// -----------------------------------------------------
// determine if AI should retreat
// -----------------------------------------------------
static t_external_string const k_text_suggest_surrender( "suggest_surrender.misc" );
static t_external_string const k_text_suggest_retreat_instead( "suggest_retreat_instead.misc" );
static t_external_string const k_text_suggest_retreat( "suggest_retreat.misc" );
static t_external_string const k_text_request_surrender( "request_surrender.misc" );

static bool suggest_retreat(  t_battlefield& battlefield, bool side )
{
	bool				enemy_towns;
	bool				blocked_towns;
	t_combat_window*	combat_window = battlefield.get_combat_window();
	t_town*				town = combat_window->find_nearest_town( side, enemy_towns, blocked_towns );
	std::string	text;

	if (battlefield.can_surrender( side ))
	{
		int					cost = battlefield.calculate_surrender_cost( side );
		std::string			cost_text = format_string( "%i", cost );
		
		text = replace_keywords( k_text_suggest_surrender, 
								 "%surrender_cost", cost_text,
								 "%town_name", town->get_name() );
		if (yes_no_dialog( text, true ))
		{
			battlefield.surrender();
			return true;
		}
	
		text = k_text_suggest_retreat_instead;
	}
	else
	{
		if (!battlefield.can_retreat( side ))
			return false;
		text = k_text_suggest_retreat;
	}
	if (no_heroes( battlefield, side ))
		return false;

	text = replace_keywords( text,  "%town_name", town->get_name() );
	if (!yes_no_dialog( text, true ))
		return false;
	if (side)
		combat_window->force_combat_termination(k_result_defender_retreated);
	else
		combat_window->force_combat_termination(k_result_attacker_retreated);
	return true;
}

static t_hero const* get_charm( t_battlefield& battlefield, bool side, t_skill& skill )
{
	t_combat_creature_list::const_iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::const_iterator	end = battlefield.creatures_end();
	t_combat_creature const*				creature;
	t_hero const*							hero;
	t_hero const*							best_hero = 0;

	skill.level = k_mastery_none;
	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->get_number() == 0 || creature->is_summoned())
			continue;
		if (creature->belongs_to_defender() != side)
			continue;
		hero = creature->get_hero();
		if (hero == 0)
			continue;

		if (hero->get_skill( k_skill_charm ) > skill.level)
		{
			skill.level = hero->get_skill( k_skill_charm );
			skill.skill = k_skill_charm;
			best_hero = hero;
		}
		if (hero->get_skill( k_skill_diplomacy ) > skill.level)
		{
			skill.level = hero->get_skill( k_skill_diplomacy );
			skill.skill = k_skill_diplomacy;
			best_hero = hero;
		}
	}
	return best_hero;
}	

static t_external_string const k_text_force_surrender( "forced_surrender.combat" );

// -----------------------------------------------------
// determine if AI should retreat
// -----------------------------------------------------
bool ai_check_retreat( t_battlefield& battlefield )
{
	bool side = battlefield.get_acting_side();

	if (battlefield.get_retreat_checked( side ))
		return false;
	if (!should_retreat( battlefield, side ))
		return false;
	battlefield.set_retreat_checked( side );

	t_player*			player = battlefield.get_player( side );
	t_combat_window*	combat_window = battlefield.get_combat_window();

	if (!player->is_computer())
		return suggest_retreat( battlefield, side );

	if (battlefield.can_surrender( side ))
	{
		int			cost = battlefield.calculate_surrender_cost( side );
		std::string	cost_text = format_string( "%i", cost );
		std::string	text;
		bool		enemy_towns;
		bool		blocked_towns;
		t_town*		town = combat_window->find_nearest_town( side, enemy_towns, blocked_towns );
		t_hero const*	enemy_hero;
		t_hero const*	hero;
		t_skill			skill;
		t_skill			enemy_skill;
		t_hero_keyword_replacer replacer;

		hero = get_charm( battlefield, side, skill );
		enemy_hero = get_charm( battlefield, !side, enemy_skill );
		replacer.add_keyword( "%surrender_cost", cost_text );
		replacer.add_keyword( "%town_name", town->get_name() );

		if (enemy_skill.level < skill.level)
		{
			replacer.add_hero( hero );
			replacer.add_skill( skill );
			text = replacer( k_text_force_surrender );
			ok_dialog( text );
			battlefield.surrender();
			return true;
		}

		text = replacer( k_text_request_surrender );
		if (yes_no_dialog( text, true ))
		{
			battlefield.surrender();
			return true;
		}
	}

	if (!battlefield.can_retreat( side ))
		return false;
	if (side)
		combat_window->force_combat_termination(k_result_defender_retreated);
	else
		combat_window->force_combat_termination(k_result_attacker_retreated);
	return true;
}
